package com.kznnc.data_structure.structure.arraystructure;

/**
 * @Description 数组结构
 *  TODO 数组实际存储的最后一个元素的下标 = 实际存储的元素个数 -1
 *  TODO 数组什么时候就满了 ?  实际元素个数 = 初始化的数组长度
 * @Author houchenkai
 * @Created Date: 2021/3/31 11:43
 * @ClassName
 */
public class ArrayStructure<T> {
    /**
     * 存放数据的数组
     */
    Object[] container;
    /**
     *   数组的实际元素个数   == 待插入元素的数组下标
     *   数组中存储元素的最后一个下标 + 1 =  数组的实际元素个数
     */
    int capacity = 0;

    public int length;

    public ArrayStructure(int size) {
        length =size;
        container = new Object[size];
    }



    public void add(T data) {
        // 扩容
        increaseSize();
        //  将需添加的元素 放到待插入元素下标的数组位置  下标加1
        container[capacity++] = data;
    }


    /**
     * [1][2][][][][][]
     * 实际存放的元素个数 == 数据初始化的长度时 进行扩容
     */
    private void increaseSize() {
        // 实际元素个数等于初始化的数组长度 说明 初始化的数组空间已经被存放满
        if (capacity == container.length) {
            Object[] newArr = new Object[capacity * 2];
            // 当数组存满时, 从数组的第一个元素遍历到最后一个存储的元素 转移到新数组中   最后一个存储的元素的下标 等于 实际元素个数-1
            for (int i = 0; i <= capacity-1; i++) {
                newArr[i] = container[i];
            }
            container = newArr;
            length =newArr.length;
        }
    }

    public T get(int index) {
        if (index < container.length) {
            return (T)container[index];
        } else {
            throw new RuntimeException("数组越界!!");
        }
    }

    public void update(int index, T data) {
        if (index < 0 || index > container.length - 1){
            throw  new RuntimeException("数组越界");
        }
        container[index] =data;
    }

    public void delete(int index){
        if (index < 0 || index > container.length - 1){
            throw  new RuntimeException("数组越界");
        }
       // 将从要删除的元素的下标的后一个 到 实际存储的最后一个元素的下标  上的元素统一前移一位  并将最后一个元素清空
        // [1][2][3]  删除index 0   将(index +1=)下标  1 到 2 (3-1 = ) 之间的元素前移
        // 先把1 移到 0 再把 2移到 1
        // i = index+1 要移到元素的开始
        for (int i = index+1; i <= capacity-1 ; i++) {
            container[i-1] =container[i];
        }
        container[capacity -1] = 0;
        capacity=capacity-1;
        reduceCapacity();
    }

    /**
     * 缩容
     */
    private void reduceCapacity(){
        int reduceCapacity =container.length/2;
        // 实际元素的个数等于数组的二分之一
        if (capacity <= reduceCapacity ){
            Object [] newArr = new Object[reduceCapacity];
            // capacity-1 = 实际存储元素下标的最后一个
            for (int i = 0; i <= capacity-1; i++) {
                newArr[i] = container[i];
            }
            container =newArr;
            length =reduceCapacity;
        }

    }


}
